package cn.fansunion.leecode.linkedlist;

/**
 * 88. 合并两个有序数组 <br/>给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
 * 
 * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 * 
 * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-2-23
 */
public class MergeSortedArray {
    /* 示例 1：
    
    输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
    输出：[1,2,2,3,5,6]
    解释：需要合并 [1,2,3] 和 [2,5,6] 。
    合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
    示例 2：
    
    输入：nums1 = [1], m = 1, nums2 = [], n = 0
    输出：[1]
    解释：需要合并 [1] 和 [] 。
    合并结果是 [1] 。
    示例 3：
    
    输入：nums1 = [0], m = 0, nums2 = [1], n = 1
    输出：[1]
    解释：需要合并的数组是 [] 和 [1] 。
    合并结果是 [1] 。
    注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
    
    提示：
    
    nums1.length == m + n
    nums2.length == n
    0 <= m, n <= 200
    1 <= m + n <= 200
    -109 <= nums1[i], nums2[j] <= 109*/
    /**
     * 思路：目标是把nums2按照顺序插入到nums1，从后向前比较插入；双指针，效率高；<br/>
     * 如果nums2有剩余的没插入，需要单独再插入<br/>
     * 如果nums1有剩余的没插入，不需要处理，特征是处理nums2，nums2没处理的自然就有序的<br/>
     * 官方算法学名：“逆向双指针”。因为算法题经常都是各种“奇思妙想”，“诡计”，突然想到：就是从后向前容易点，逐步替换“0”的过程
     * 这道题的“合并数组”，又是有特定要求的；常见的合并数组：nums1+nums2，可以直接new一个nums3,正向遍历nums1和nums2
     * 
     * 
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int nums1Index = m - 1;
        int nums2Index = n - 1;
        int curIndex = m + n - 1;
        while (nums1Index >= 0 && nums2Index >= 0) {
            if (nums1[nums1Index]<= nums2[nums2Index]) {
                nums1[curIndex] = nums2[nums2Index];
                nums2Index--;
                curIndex--;
            } else {
                nums1[curIndex] = nums1[nums1Index];
                nums1Index--;
                curIndex--;
            }
        }
        // nums1提前往后挪了，nums2还有剩下的
        // 这种题目，边界值的情况经常有，一次性想不全，必须得构造很多测试用例额
        while (nums2Index >= 0) {
            nums1[nums2Index] = nums2[nums2Index];
            nums2Index--;
        }
    }

    /**
     * 合并两个有序数组（笨办法），结果还不对<br/>
     * [-1,0,0,3,3,3,0,0,0] 6,[1,2,2] 3；输出：[1,2,2,-1,0,0,3,3,3]，预期：[-1,0,0,1,2,2,3,3,3]
     * 
     * @param nums1
     *            nums1 = [1,2,3,0,0,0]
     * @param m
     *            3 nums2 = [2,5,6]
     * @param nums2
     *            3
     * @param n
     *            3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。
     */
    public void mergeStupidAndError(int[] nums1, int m, int[] nums2, int n) {
        // 遍历需要插入的若干数字
        for (int nums2Index = 0; nums2Index < n; nums2Index++) {
            // 插入1个数字到目标数组里
            mergeIntoNums(nums2[nums2Index], nums1);
        }
    }

    // 插入1个数字到目标数组里
    private void mergeIntoNums(int newNum, int[] nums) {
        // 先找插入位置
        int insertIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0 || newNum < nums[i]) {
                insertIndex = i;
                break;
            }
            insertIndex++;
        }
        // 通过2个临时变量的辅助，插入，效果：后面的数字都往后移一位
        int cur = newNum;
        int next = 0;
        for (int index = insertIndex; index < nums.length; index++) {
            next = nums[index];
            nums[index] = cur;
            cur = next;
        }
    }

    /**
     * 另外一种形式的合并数组，允许构造新的merge数组并返回，稍微简单点
     * 
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] mergeWithReturn(int[] nums1, int[] nums2) {
        int[] nums = new int[nums1.length + nums2.length];
        int nums1Index = 0;
        int nums2Index = 0;
        int curIndex = 0;
        // 双指针
        while (nums1Index < nums1.length && nums2Index < nums2.length) {
            if (nums1[nums1Index] <= nums2[nums2Index]) {
                nums[curIndex] = nums1[nums1Index];
                nums1Index++;
            } else {
                nums[curIndex] = nums2[nums2Index];
                nums2Index++;
            }
            curIndex++;
        }
        // num1有剩余的
        while (nums1Index < nums1.length) {
            nums[curIndex] = nums1[nums1Index];
            nums1Index++;
            curIndex++;
        }
        // nums2有剩余的
        while (nums2Index < nums2.length) {
            nums[curIndex] = nums2[nums2Index];
            nums2Index++;
            curIndex++;
        }
        return nums;
    }

}
